package complexite;

import java.util.Collections;
import java.util.Random;

public class RandomQuickSelect {

	
	

	public static void echange (ExtArrayList az,int num1,int num2){
		Collections.swap(az, num1,num2);
	}
	
	
	
	public static int SelectionRandom (ExtArrayList a,int p, int r,int i){
		if(p==r)
			return a.get(p);
		
		int piv= p + new Random().nextInt((r - p) + 1);
		
		int q = PartitionR(a,p,r,piv);
		
		int k=q-p+1;
		
		if(i==k)
			return a.get(q);
		else if(i<k)
			return SelectionRandom(a, p, q-1, i);
		else
			return SelectionRandom(a, q+1, r, i-k);
	}
	
	public static int PartitionR (ExtArrayList a, int p,int r,int i){
		
		echange(a,r,i);
		
		int x=a.get(r);
		i=p-1;
		
		for(int j=p;j<r;j++){
			if(a.get(j) < x){
				i++;
				echange(a,i,j);
			}
		}
		echange(a,i+1,r);
		return i+1;
	}
	
		
	public static void main (String args[]){
		ExtArrayList az = new ExtArrayList();
		az.getArray(11, 10, 30);
		System.out.println("pas trié: " +az);
		System.out.println((az.size()+1)/2);
		System.out.println(SelectionRandom(az,0,az.size()-1,(az.size()+1)/2));
		System.out.println("trié    : " + az);
	}
	
	
}
